package offer

/*
时间复杂度：O(N)
空间复杂度：O(N)

前缀和+hash

1.如果存在连续子数组[i...j]的和为k，则preSum[j]-preSum[i-1]==k,即preSum[i-1]==preSum[j]-k,
	假设当前遍历到j，则等价于找到值为preSum[j]-k的前缀和的个数,
2.可以在遍历nums时，通过一个变量动态更新当前前缀和的值（不必用数组存储所有前缀和）,
同时通过hash记录每次出现的前缀和的个数，从而通过hash求出值为preSum[j]-k的前缀和的总个数

问题：为什么不能使用滑动窗口？？？
使用滑动窗口，right右移一定要使得sum能增大（严格递增）且left右移使sum变小（严格递减）
而nums中元素范围是-1000 <= nums[i] <= 1000, 不能满足滑动窗口的条件
*/

func subarraySum(nums []int, k int) int {
	hash := make(map[int]int)
	hash[0]++
	sum := 0
	ans := 0
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
		ans += hash[sum-k]
		hash[sum]++
	}
	return ans
}
